/*
https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/solution/you-xu-ju-zhen-zhong-di-kxiao-de-yuan-su-by-leetco/
 */
public class Solution378 {
    public int kthSmallest(int[][] matrix, int k) {
        int l=-1000000000,r=1000000000;
        int ans=Integer.MAX_VALUE;
        while (l<=r){
            int mid=(l+r)/2;
            if (check(mid,matrix,k)){
                ans=mid;
                r=mid-1;
            }else{
                l=mid+1;
            }
        }
        return ans;
    }

    boolean check(int mid,int[][] matrix,int k){
        int i=matrix.length-1,j=0,sum=0;
        while (valid(i,j,matrix.length,matrix[0].length)){
            if (mid>=matrix[i][j]){
                sum=sum+i+1;
                j++;
            }else{
                i--;
            }
        }
        return sum>=k;
    }

    private boolean valid(int i, int j, int m, int n) {
        return i>=0 && j>=0 && i<m && j<n;
    }

    public static void main(String[] args) {
        System.out.println(new Solution378().kthSmallest(new int[][]{{1,5,9},{10,11,13},{12,13,15}},8));
    }
}
